1. Field of the Invention
The present invention relates to a method for re-synchronizing a variable length code at a high speed using a parallel-processing pattern matching when a transmission error is involved in the variable length code received in a variable length decoder used in broad band-integrated service digital network (B-ISDN) terminal, high definition TV, digital TV, multimedia, Videotex, facsimile and etc..
2. Description of the Prior Art
Currently, all of data having statistical redundancy are transmitted under a condition that they are compressed using variable length codes in order to achieve a maximized transmission efficiency. However, such variable length codes may cause delay of a transmission error involved therein. Where a transmission error is involved in a variable length code, a synchronous code having a fixed length is additionally used in order to minimize the propagation of the transmission error.
Variable length codes are made by allocating a small amount of bits to symbols of high generation rate while allocating a large amount of bits to symbols of low generation rate in accordance with the statistical distribution of the symbols to be coded. Use of variable length coding results in an effective bit rate reduction, as compared to use of fixed length coding. As the variable length codes remove the statistical redundancy of data, it can reduce greatly a large quantity of video and audio data being transmitted via a transmission medium or stored in a recording medium.
However, the variable length coding has the following disadvantages. First, when a bit string with variable length codes is decoded, it is decoded in the form of symbols having different lengths depending on the statistical distribution of the symbols. For this reason, the decoder used to decode the bit string has an increased complexity in hardware. Second, where a transmission error is generated, the code string is decoded in the form of codes having lengths other than those of the original codes to be transmitted. The transmission error affects next codes continuously until the decoder recognizes this transmission error.
The variable length coder adds a synchronous code having a fixed length to a variable length code in order to prevent any data processing delay caused by the transmission error. On the other hand, the variable length decoder searches the synchronous code upon recognizing the transmission error involved in the variable length code and thereby carries out a re-synchronization with the variable length code. In the case of the shift from one channel to another channel, the variable length decoder requires the operation of the re-synchronization with the variable length code. Once the variable length decoder achieves the re-synchronization with variable length codes, the variable length codes can be correctly decoded. Where a processing at high speed is required as in B-ISDN terminal and multimedia, the high speed re-synchronization algorithm enables the decoder to rapidly deal with the transmission error.
Existing sequential pattern matching algorithm is unsuitable for a direct application to systems requiring a high processing speed such as B-ISDN terminal, high definition TV and multimedia because its processing speed is low. This problem will now be described in conjunction with FIG. 1. The input bit string S(t) is compared with the synchronous code pattern PAT. Where the input bit string S(t) does not accord with the synchronous code pattern PAT, it is shifted one bit. Thereafter, the shifted input bit string S(t+1) is compared with the synchronous code pattern PAT. Where the input bit string S(t+1) does not accord with the synchronous code pattern PAT, it is shifted one bit again. In such a manner, the input bit string S(t+n) is repeatedly compared to the synchronous code pattern PAT and then shifted until they accord with each other.
Where the input bit string, namely, character string S is assumed to be "s1, s2, s3, . . . si-1, si, si+1, si+2, . . . sL" and the match pattern PAT to be found from the character string S is assumed to be "p1, p2, p3, p4, . . . pn" (n&lt;L), "si+1" of the character string S is compared with "p1" of the match pattern PAT. If "si+1" to "si+3" accord with "p1" to "p3", respectively, while "si+4" does not accord with "p4", it is regarded that the pattern matching has been failed. In this case, the founding of the match pattern PAT is begun from "si+2" of the character string S again. That is, "si+2" is compared with "p1". After this procedure is repeated for all characters of the character string S, the match pattern PAT is shifted by "L-n+1" for the pattern matching. Assuming that the number of comparing operations for one time shift is K, the value K corresponds to "1" when the first patterns being compared with each other, namely, "p1" and "si+1" are different from each other. In the worst case, namely, the case wherein the character string S does not accord with "pn" of the match pattern PAT while according with the match pattern PAT up to "pn-1", the value K is "n". In the above-mentioned case, the value K is 3 because the character string S and match pattern PAT accord with each other up to "si+3" and "p3". Accordingly, the range of the value K can be expressed as follows: EQU 1.ltoreq.K.ltoreq.n
Therefore, the number of total operations can be calculated by the following equation (1): ##EQU1##
The value K is dependant on the characteristic of character string to be compared. If the character string is the binary random bit string, the mean value of K's can be expressed by the following equation (2): ##EQU2##
By referring to the above equation, it can be found that the value K is reduced in increase degree as the value t is increased. If the value n is infinite (.infin.), the mean value of K's is "2". In accordance with the former algorithm, the character string S should be compared from "si+2" thereof with "p1" of the match pattern PAT. This algorithm also has the disadvantage of controlling the buffer stored with the character string S in terms of hardware.
The latter algorithm has the advantage that a desired match pattern PAT can be rapidly found out from the character string S. In accordance with this algorithm, it is possible to easily control the buffer stored with the character string S in terms of hardware. The basic concept of this algorithm is as follows.
Where "si+5" does not accord with "p5" while "si+1" to "si+4" accord with "p1" to "p4", respectively, the number of comparing operations can be reduced if information about "p1" to "p4" is known, only by comparing "si+5" with pk (k&lt;5) without the comparison between "si+2" and "p1". In this case, no buffer control is required because "si+1", "si+2", "si+3" and "si+4" of the character string S already compared require any comparison no longer. In this case, the function stipulating for the relation between "si+5" and "pk" is defined as the failure function F().
Definition 1: where a match pattern PAT of "p1, p2, p3, p4, . . . pn" is given, the failure function F() for this pattern is defined as follows: EQU if "p1, p2, p3, . . . , pk"="pj-k+1, pj-k+2, . . . " (if k.gtoreq.1) F(j)=k
otherwise EQU F(j)=0 (3)
For example, if PAT="a,b,c,a,b,c,a,c,a,b", the following failure function can be obtained:
j: 12345678910 PA1 PAT: abcabcacab PA1 F(j): 0001234012
Where pattern matching is failed, the location of a next comparing pattern can be obtained from the following equation (4) using the above failure function:
if j=1
Next Location (j)=0,
if j.noteq.1, EQU (j)=F(j1)+1 (4)
For example, it can be found that where the match pattern PAT is pattern matched with a next character string S of ". . . a,b,c,a,c,b,c,a,c,c,a,c,a,b, . . . ", "p5" (p5=b) does not accord with "si+5" (si+5=c). In this case, the location of the next comparing pattern can be derived from the above equation as follows: EQU F(5-1)+1=2
Accordingly, the number of comparing operations can be minimized by comparing "p2" (p5=b) and "si+5" (si+5=c) again without comparing the character string S from "si+2" thereof with "p1" of the match pattern PAT again.
Use of the failure function provides two advantages. The first advantage is that where the pattern matching is failed, the part of the character string S already compared is unnecessary to be compared. Accordingly, it is easy to control the buffer stored with the character string S. The second advantage is that the number of operations is minimized using the failure function.
Heretofore, the general sequential pattern matching algorithm and the sequential pattern matching algorithm using the failure function have been described. However, these algorithms are practically unsuitable for a direct application to systems requiring a high processing speed such as B-ISDN terminal, high definition TV and multimedia because its processing speed is low. Where such algorithms are realized in the form of hardware, it is possible to simultaneously compare "si+1, . . . , si+n" with "p1, . . . , pn" at one clock. Algorithms generally used utilize the sequential algorithm described in conjunction with Definition 1. In accordance with this method, the match pattern PAT of "p1, p2, . . . , pn" are simultaneously compared with the character string S of "si+1, si+2, . . . , si+n" to check the accord between the match pattern PAT and the character string S at one clock. If the match pattern PAT and the character string S do not accord with each other, the character string S is shifted one character. Thereafter, the match pattern PAT is compared with the character string S of "1+2, . . . , i+n+1". If no accord is obtained between the match pattern PAT and the character string S, the above procedure is then repeated. This procedure is illustrated in FIG. 1. In this case, the number of total shirt times of the match pattern PAT for the comparison with the character string S is "L-n+1". Accordingly, the number of operations to be required is "(L-n+1).times.n". The above algorithm enables the shift of one character for one clock.
As described above, the conventional method requires a lot of time to search for a synchronous code having a fixed length for a variable length code involving a transmission error. As a result, this method has a limitation on an application to systems requiring a high processing speed.